// 本能 indexOf
var strStr = function (haystack, needle) {
  return haystack.indexOf(needle);
};

// substring()
var strStr = function (haystack, needle) {
  if (needle == "") return 0;
  let haystackLen = haystack.length;
  let needleLen = needle.length;
  for (let i = 0; i < haystackLen; i++) {
    if (haystack[i] === needle[0]) {
      if (haystack.substring(i, i + needleLen) === needle) return i;
    }
  }
  return -1;
};

// KMP 算法
var strStr = function (haystack, needle) {
  if (needle === "") return 0;
  if (haystack === "") return -1;

  let needleLen = needle.length;
  let haystackLen = haystack.length;
  let offset = [];

  // 计算偏移量
  for (let i = 0; i < needleLen; i++) {
    for (let j = 0; j <= i; j++) {
      if (needle[j] !== needle[i - j]) {
        offset[i] = j + 1;
        break;
      }
      if (j == i && needle[j] === needle[i - j]) {
        offset[i] = j + 1;
      }
    }
  }

  for (let i = 0; i < haystackLen; ) {
    for (let j = 0; j < needleLen; j++) {
      if (needle[j] !== haystack[i + j]) {
        i += offset[j];
        break;
      }
      if (j == needleLen - 1 && needle[j] === haystack[i + j]) {
        return i;
      }
    }
  }
  return -1;
};
